package com.leetcode;

/**
 * 821. 字符的最短距离
 * 问题可以转换成，对 s 的每个下标 i，求
 *
 * s[i] 到其左侧最近的字符 c 的距离
 * s[i] 到其右侧最近的字符 c 的距离
 * 这两者的最小值
 *
 * @author fy
 * @date 2022/4/20 20:44
 */
public class Solution821_1 {

    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];

        for (int i = 0, idx = -n; i < n; ++i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = i - idx;
        }

        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = Math.min(ans[i], idx - i);
        }
        return ans;
    }

}
